1. Field of the Invention
The present invention relates to an encoding/decoding system adapted to encode and decode signals with a high efficiency and, in particular, to an encoding/decoding system which improves an encoding efficiency by utilizing local properties between the signals.
2. Description of Prior Art
As basic technologies for encoding input information with a high efficiency by suppressing redundant information, methods of variable length encoding and vector quantization are known.
FIG. 1 is a block diagram schematically illustrating the constitution of an encoding/decoding system according to the prior art. In FIG. 1, an encoding section 200 comprises an encoder 202 and a variable length encoder 204, while a decoding section 206 comprises a variable length decoder 208 and a decoder 210.
Operation of this system will next be explained.
An input signal 212 is encoded with a high efficiency by the encoder 202 to provide encoded data 214. The encoded data 214 is, in turn, subjected to variable length encoding by the variable length encoder 204 and transmitted as code word 216.
At the side of the decoder 206 on the other hand, the code word 216 transmitted from the encoding section 200 is subjected to variable length decoding by the variable length decoder 208 and decoded by the decoder 210 to provide an output signal 218.
The allocation of the variable length codes is executed at the variable length encoder 204 depending on the probability of occurrence of such encoded data in such a way that a shorter code word is allocated to data having a higher rate of occurrence and a longer code word is allocated to data having a lower rate of occurrence.
The encoding/decoding system as explained above does not utilize such local properties of the input signals that if there is a correlation between adjacent signals, the probability of the same value occurring consecutively is expected to be high. Accordingly, the encoding efficiency is not sufficiently high.
Vector quantization is known as a technology of band compression encoding of image signals. FIG. 2 is a block diagram schematically illustrating a general constitution of an encoding/decoding system which employs vector quantization technology. An encoding section 220 comprises a vector quantization encoder 222 and a code book 224, while a decoding section 226 comprises a vector quantization decoder 228 and a code book 230. The code books 224, 230 are memories which store a plurality of quantization representative vectors and adapted to provide read quantization representative vectors to the vector quantization encoder 222 and the vector quantization decoder 228. The vector quantization encoder 222 is adapted to vector-quantize an input vector 232 by using the quantization representative vectors supplied from the code book 224 and output an index of the quantization representative vector as encoded data. On the other hand, the vector quantization decoder 228 is adapted to decode the received index in accordance with the quantization representative vectors supplied from the code book 230 and reproduce a signal as a decoded vector 234.
An operation of the system constituted as described above will next be explained.
Now, assuming an input K dimensional vector 232 is to be expressed as follows: EQU X=[X.sub.1,X.sub.2, . . . ,X.sub.K ] (1)
A representative quantization vector Y.sub.i stored in the code book 224 is assumed to be expressed as follows: EQU Y.sub.i =[Y.sub.i1,Y.sub.i2, . . . ,Y.sub.iK ] (2)
A set of this vector Y.sub.i is expressed as EQU [Y]=[Y.sub.1,Y.sub.2, . . . ,Y.sub.N ] (3)
In this case, at the vector quantization encoder 222, an index i of the respective quantization vector which enables a distortion di of the input vector 232 defined by the following equation to be minimum is decided: ##EQU1## provided d.sub.i &lt;d.sub.l for all l.noteq.i.
From the vector quantization encoder 222, the index i for identifying the representative quantization vector Y.sub.i is output and transmitted as the encoded data.
As explained above, the transmitted encoded data are input to the vector quantization decoder 228. In this decoder, the representative quantization vector Y.sub.i corresponding to the index i provided by the encoded data is read out of the code book 230 and the decoded vector 234 is reproduced as a vector expressed by the following equation: EQU X=Y.sub.i ( 5)
According to the vector quantization system as explained above, when the number of dimension is high, it is difficult to completely optimize all the definite number of representative quantization vectors to be stored in the code books 224, 230 for all the input vectors. Besides, encoding efficiency is not satisfactory since such local properties of the input vectors as a correlation between the adjacent input vectors and the line are not taken into consideration.
FIG. 3 is a block diagram illustrating an example of the constitution of the vector quantization encoding section 220 and FIG. 4 is a block diagram illustrating an example of the constitution of the vector quantization decoding section 226. In FIG. 3, a mean value separation circuit 236 is used to separate a mean value from the input vector 232. A code book 224 stores normalized output vectors. The address for reading the code book 224 are provided by an address counter 238. Inner products of the input vector from which the mean value has been separated and the normalized output vectors are obtained by an inner product calculating circuit 240. A maximum inner product detection circuit 242 detects the largest inner product among the inner products and outputs a detection signal to an index latch 244 as well as outputting the inner product value at this instance as a gain. An output from the address counter 238 is then latched in the index latch 244 as a vector quantization index as a result of vector quantization of its input vector 232 in accordance with the detection signal output from the maximum inner product detection circuit 242. The mean value of the input vector 232 and the maximum inner product value (gain) are DPCM-encoded by the DPCM encoding circuits 246, 248, respectively. The DPCM encoded mean value, DPCM encoded gain and the index are then subjected to variable length encoding by a variable length encoding circuit 250 and are thereby output as encoded data 252. The encoded data 252 transmitted from the encoder 250 are, in turn, subjected to variable length decoding by a variable length decoding circuit 254. The variable length decoded mean value and gain are then subjected to DPCM decoding by the DPCM decoding circuits 256, 258, respectively. The variable length decoded index is latched by an index latch 260 and a normalized output vector corresponding to the index is output from the code book 230. The product of the decoded normalized output vector and the decoded gain is obtained by a gain factor multiplier 262. An output from the gain factor multiplier 262 and the decoded mean value are added at a mean value adder 264 and a decoded reproduced vector 266 is obtained.
An operation of the system as described above will next be explained.
From a sequence of signals 232 input as a K dimensional input vector S=[S.sub.1, S.sub.2, . . . , S.sub.K ], the mean value .mu. is separated by the mean value separation circuit 236 and the input vector is converted to a vector X*. Those .mu. and X* are expressed as follows: ##EQU2##
The DPCM encoding circuit 246 removes any redundancy from the mean value .mu. and DPCM signal .epsilon..sub..mu. is output therefrom. The mean-value-separated vector X* is subjected to the following vector quantization encoding processing by the inner product calculating circuit 240. Firstly, a mean value .mu. is separated from the input vector formed from a model sequence of signals S so as to produce the mean-value-separated vector X*. Then, a set of a plurality of normalized output vectors y.sub.i (i=1, 2, . . . , N) is produced by using a clustering method based on the statistical characteristics of a normalized vector X which is formed by normalizing the vector X* by the amplitude component of the vector X*, i.e., the standard deviation .sigma.. The thus produced set is written in the code book 224. Those .sigma., X and X* are expressed as follows: ##EQU3##
At the time when the mean-value-separated vector X* is input to the inner product calculating circuit 240, the address counter 238 outputs the address information i in the order of i=1, 2, . . . , N and the normalization output vector y.sub.i corresponding to each address information i is read out from the code book 224. Then the inner product P (X*, y.sub.i) of the mean-value-separated vector X* and N normalization output vectors y.sub.i is calculated by the inner product calculating circuit 240 in accordance with the following equation and the results of the calculation are compressed successively with each other. ##EQU4##
The maximum inner product P.sub.max is detected by the maximum inner product detection circuit 242 among N inner products obtained as a result of the calculation, and the address information i corresponding to the maximum inner product is taken as the detection signal in the index latch 244 which in turn outputs the normalization output index i. The maximum inner product P.sub.max detected is then input to DPCM encoding circuit 248 as the gain g, and the redundant component is removed from the maximum inner product, the DPCM signal .epsilon..sub.g is output.
The DPCM signal .epsilon..sub..mu. of the mean value, the DPCM gain .epsilon..sub.g and the index i of the normalized output vector are subjected to variable length encoding by the variable length encoding circuit 250 and transmitted as the encoded data 252.
An operation of the vector quantization decoding will next be explained.
Firstly, the DPCM signal .epsilon..sub..mu. of the mean value .mu., the DPCM signal .epsilon..sub.g of the gain g and the index i of the normalization output vector are decoded successively by the variable length decoding circuit 254 from the encoded data 252 which have been transmitted from the encoding section 220.
Then a value .mu. corresponding to the mean value .mu. is decoded and reproduced by DPCM decoding circuit 256. Also, a value g.sub.i corresponding to the gain g.sub.i is decoded and reproduced by DPCM decoding circuit 258.
The decoded index i of the normalization output vector is taken into the index latch 260 which causes the normalization output vector y.sub.i corresponding to the normalization output vector index i to be read out of the code book 230 in which the same content as the code book 224 is written.
The decoded gain g.sub.i is multiplied with the normalization output vector y.sub.i at the gain factor multiplier 262 and the resulting product is added to the decoded mean value .mu. at the mean value adder 264 whereby the decoded reproduced vector S can be obtained. In other words, the following operations are executed: EQU S.sub.j =g.sub.i .multidot.y.sub.ij +.mu. EQU S=[S.sub.1,S.sub.2, . . . ,S.sub.K ]
In the vector quantization encoding/decoding system constituted as explained above, the variable length code allocation is executed without utilizing such local inclinations that the same values are successively selected due to correlation between adjacent vectors, and this is disadvantageous in respect of encoding efficiency.
As explained above, local properties such as a correlation between input signals are not utilized in the encoding/decoding systems according to the prior art.
In the meantime, the Japanese Patent Publication No. 63-26951 published on June 1, 1988 discloses an interframe encoding system adapted to encode image signals with a high efficiency by utilizing a correlation among the image signals in consecutive frames. According to this interframe encoding system, as shown in FIG. 5, 4.times.4 samples on adjacent four scanning lines in the n-th frame are grouped into a block. This block forms a vector S.sub.n =[S.sub.1, S.sub.2, . . . , S.sub.16 ].sub.n, and is designated as A.sub.f.sup.n indicating that this block is the f-th block in the n-th frame. Similarly, samples in a block A.sub.f.sup.n+1 located at the same position in the (n+1)-th frame as that of the block A.sub.n in the n-th frame are designated as a vector S.sub.n+1 =[S.sub.1, S.sub.2, . . . , S.sub.16 ].sub.n+1. Then the respective samples of the image signal vector S.sub.n in the n-th frame are subtracted from the corresponding samples of the image signal vector S.sub.n+1 in the (n+1)-th frame, so that an interframe differential signal vector X.sub.n+1 =[X.sub.1, X.sub.2, . . . , X.sub.16 ].sub.n+1 is obtained. This signal vector X.sub.n+1 is vector-quantized in the 16-dimensional Euclidean signal space, whereby a highly efficient encoding or the reduction in bit rate can be realized.
FIG. 6 is a block diagram schematically illustrating the constitution of an encoder employed in such an interframe encoding system. In FIG. 6, the reference numeral 268 designates a scan converting buffer adapted to convert raster scanning to block scanning; 270 a subtracter adapted to execute subtraction between frames; 272 a vector quantization encoder; 274 a vector quantization decoder; 276 an adder adapted to execute addition between frames; and 278 a frame memory adapted to temporarily store a sequence of signals decoded locally.
An operation of this system will next be explained. A sequence of input digital image signals 280 is rearranged by the scan converting buffer 268 from the order of raster scanning to the order of block scanning. In other words, the horizontally scanned image signals are converted in such an order that the sequence of the signals contained in the block A.sub.n as shown in FIG. 5 is serially arranged. At the subtracter 270, a signal sequence 284 previously encoded and decoded is subtracted as a predicted signal sequence from the sequence of signals 282 arranged in the order of block scanning. Then a predicted error signal sequence 286 thus obtained is subjected to vector quantization at the vector quantization encoder 272, whereby the vector quantization index 288 is output. The vector quantization index 288 is decoded by the vector quantization decoder 274 and added to the predicted signal sequence 284 to become a decoded image signal sequence 290 which is temporarily stored in the frame memory 278 for use in prediction of the next frame. The operation as explained above will be described more specifically by referring to FIG. 5. When the block of the present frame A.sub.f.sup.n is input, the decoded block A.sub.f.sup.n-1 located at the same space position is used as the predicted signal sequence and a differential block A.sub.f.sup.n -A.sub.f.sup.n-1 is subjected to vector quantization. Then the predicted block A.sub.f.sup.n-1 and the differential block are added and the block A.sub.f.sup.n of the present frame is decoded. In other words, a sequence of decoded signals of one frame is utilized for prediction of a sequence of signals for the next frame.
FIG. 7 is a block diagram schematically illustrating the constitution of a decoder adapted to reproduce signals corresponding to those transmitted from the encoder shown in FIG. 6. In FIG. 7, the reference numeral 292 designates a vector quantization decoder; 294 an adder adapted to execute addition between frames; 296 a frame memory adapted to temporarily store a sequence of signals locally decoded; 298 a scan converting buffer adapted to rearrange a sequence of decoded signals from the block scanning to the raster scanning.
At the side of the decoder, the vector quantization index 288 is decoded by the vector quantization decoder 292 and added to the predicted signal sequence read out of the frame memory 296 to provide the decoded image signal sequence. The decoded image signal sequence is rearranged by the scan converting buffer 298 from the order of block scanning to the order of raster scanning.
In this interframe encoding system, a correlation between the signals in the consecutive frames is obtained in accordance with interframe prediction. More specifically, a spatial correlation between the consecutive frames is applied to vector quantization by predicting the image signal of the present frame based on the signal decoded as the image signal of the frame immediately before the present frame whereby data compression is achieved. In this system, instead of utilizing the blocks located at the same positions of the consecutive frames, a movement compensation method wherein displacement (movement) is taken into consideration for attaining the maximum prediction efficiency or a random control method which does not encode all consecutive frames may be employed.
However, with regard to encoding and decoding according to the system as described above, time correlation between image signals is not fully utilized. Moreover, it is necessary to decode all the signals, starting from the first frame, and any undesired influence caused by an error such as noise may be propagated throughout decoding operation.